08. Graph Representation Practice
Graph Representation Practice
Question:
You should become comfortable with various graph representations—graphs crop up often in interviews and in computer science in general, and you could need to represent it in any of it's forms.
In this exercise you'll need to add functions to a
Graph
class to return various representations of the same graph. Your graph will have two different components:
Nodes
and
Edges
.
class Node(object):
def __init__(self, value):
self.value = value
self.edges = []
Nodes are pretty much the same as they were in trees. Instead of having a set number of children, each node has a list of
Edges
.
class Edge(object):
def __init__(self, value, node_from, node_to):
self.value = value
self.node_from = node_from
self.node_to = node_to
Here, we assume that edges have both a value and a direction. An edge points from one node to another—the node it starts at is the
node_from
and the node it ends at is the
node_to
. You can envision it as
node_from -> node_to
.
The base of the
Graph
class looks something like this:
class Graph(object):
def __init__(self, nodes=[], edges=[]):
self.nodes = nodes
self.edges = edges
A
Graph
class contains a list of nodes and edges. You can sometimes get by with just a list of edges, since edges contain references to the nodes they connect to, or vice versa. However, our
Graph
class is built with both for the following reasons:
-
If you're storing a disconnected graph, not every node will be tied to an edge, so you should store a list of nodes.
-
We could probably leave it there, but storing an edge list will make our lives much easier when we're trying to print out different types of graph representations.
Unfortunately, having both makes insertion a bit complicated. We can assume that each value is unique, but we need to be careful about keeping bothnodes
andedges
updated when either is inserted. You'll also be given these insertion functions to help you out:def insert_node(self, new_node_val): new_node = Node(new_node_val) self.nodes.append(new_node) def insert_edge(self, new_edge_val, node_from_val, node_to_val): from_found = None to_found = None for node in self.nodes: if node_from_val == node.value: from_found = node if node_to_val == node.value: to_found = node if from_found == None: from_found = Node(node_from_val) self.nodes.append(from_found) if to_found == None: to_found = Node(node_to_val) self.nodes.append(to_found) new_edge = Edge(new_edge_val, from_found, to_found) from_found.edges.append(new_edge) to_found.edges.append(new_edge) self.edges.append(new_edge)
Alright, time to code the rest!
Start Quiz:
class Node(object):
def __init__(self, value):
self.value = value
self.edges = []
class Edge(object):
def __init__(self, value, node_from, node_to):
self.value = value
self.node_from = node_from
self.node_to = node_to
class Graph(object):
def __init__(self, nodes=[], edges=[]):
self.nodes = nodes
self.edges = edges
def insert_node(self, new_node_val):
new_node = Node(new_node_val)
self.nodes.append(new_node)
def insert_edge(self, new_edge_val, node_from_val, node_to_val):
from_found = None
to_found = None
for node in self.nodes:
if node_from_val == node.value:
from_found = node
if node_to_val == node.value:
to_found = node
if from_found == None:
from_found = Node(node_from_val)
self.nodes.append(from_found)
if to_found == None:
to_found = Node(node_to_val)
self.nodes.append(to_found)
new_edge = Edge(new_edge_val, from_found, to_found)
from_found.edges.append(new_edge)
to_found.edges.append(new_edge)
self.edges.append(new_edge)
def get_edge_list(self):
"""Don't return a list of edge objects!
Return a list of triples that looks like this:
(Edge Value, From Node Value, To Node Value)"""
return []
def get_adjacency_list(self):
"""Don't return any Node or Edge objects!
You'll return a list of lists.
The indecies of the outer list represent
"from" nodes.
Each section in the list will store a list
of tuples that looks like this:
(To Node, Edge Value)"""
return []
def get_adjacency_matrix(self):
"""Return a matrix, or 2D list.
Row numbers represent from nodes,
column numbers represent to nodes.
Store the edge values in each spot,
and a 0 if no edge exists."""
return []
graph = Graph()
graph.insert_edge(100, 1, 2)
graph.insert_edge(101, 1, 3)
graph.insert_edge(102, 1, 4)
graph.insert_edge(103, 3, 4)
# Should be [(100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4)]
print graph.get_edge_list()
# Should be [None, [(2, 100), (3, 101), (4, 102)], None, [(4, 103)], None]
print graph.get_adjacency_list()
# Should be [[0, 0, 0, 0, 0], [0, 0, 100, 101, 102], [0, 0, 0, 0, 0], [0, 0, 0, 0, 103], [0, 0, 0, 0, 0]]
print graph.get_adjacency_matrix()
Solution:
Here's the solution:
def get_edge_list(self):
edge_list = []
for edge_object in self.edges:
edge = (edge_object.value, edge_object.node_from.value, edge_object.node_to.value)
edge_list.append(edge)
return edge_list
def get_adjacency_list(self):
max_index = self.find_max_index()
adjacency_list = [None] * (max_index + 1)
for edge_object in self.edges:
if adjacency_list[edge_object.node_from.value]:
adjacency_list[edge_object.node_from.value].append((edge_object.node_to.value, edge_object.value))
else:
adjacency_list[edge_object.node_from.value] = [(edge_object.node_to.value, edge_object.value)]
return adjacency_list
def get_adjacency_matrix(self):
max_index = self.find_max_index()
adjacency_matrix = [[0 for i in range(max_index + 1)] for j in range(max_index + 1)]
for edge_object in self.edges:
adjacency_matrix[edge_object.node_from.value][edge_object.node_to.value] = edge_object.value
return adjacency_matrix
def find_max_index(self):
max_index = -1
if len(self.nodes):
for node in self.nodes:
if node.value > max_index:
max_index = node.value
return max_index